<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      var longestCommonSubsequence = function (text1, text2) {
        // 定义dp函数 dp[s1,i,s2,j] 为 字符串 s1 从i开始 和 字符串s2 从j 开始的 最长公共子序列
        var memo = {};
        var str = "";
        return dp(text1, 0, text2, 0);

        // 优化重叠子问题 备忘录
        function dp(s1, i, s2, j) {
          if (i == s1.length || j == s2.length) {
            return 0;
          }
          var key = "" + i + j;
          if (memo[key] == undefined) {
            if (s1[i] == s2[j]) {
              memo[key] = dp(s1, i + 1, s2, j + 1) + 1;
            } else {
              memo[key] = Math.max(dp(s1, i, s2, j + 1), dp(s1, i + 1, s2, j));
            }
          }
          console.log(memo);
          return memo[key];
        }
      };
      console.log(
        longestCommonSubsequence(
          "ixefcvarevabmfabqfivodqfaluxqp",
          "cxwfkzyxabytijcnohgzgbchwpshwnu"
        )
      );
    </script>
  </body>
</html>
